package sort;

public class MergeSortExercise {

    private static int[] tempArr;
    public int[] sortArray(int[] nums) {
        tempArr = new int[nums.length];
        sort(nums,0,nums.length-1);
        return nums;
    }

    private static void sort(int[] nums, int lo, int hi) {
        if(lo==hi){
            return;
        }
        int mid = (lo+hi)/2;
        sort(nums,lo,mid);
        sort(nums,mid+1,hi);
        mergeHere(nums,lo,mid,hi);
    }

    private static void mergeHere(int[] nums, int lo, int mid, int hi) {
        for (int i = 0; i < tempArr.length; i++) {
            tempArr[i] = nums[i];
        }

        int left = lo,right = mid +1;
        for (int i = lo; i <= hi; i++) {
            if(left == mid+1){
                nums[i] = tempArr[right++];
            }else if (right == hi+1 ){
                nums[i] = tempArr[left++];
            } else if (tempArr[left] > tempArr[right]) {
                nums[i] = tempArr[right++];
            }else {
                nums[i] = tempArr[left++];
            }
        }

    }
}
